package 回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class solu {
    private ArrayList<List<Integer>> res;
    private boolean []used;


    public List<List<Integer>> permute(int[] nums) {
        if(nums == null) return res;
        used = new boolean[nums.length];
        per(nums, 0, new LinkedList<Integer>());
        return res;
    }
    public void per(int[] nums, int index, LinkedList<Integer> list) {
        if(index == nums.length){
            res.add((LinkedList<Integer>)list.clone());
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!used[i]){
                list.addLast(nums[i]);
                used[i] = true;
                per(nums, index+1, list);
                list.removeLast();
                used[i] = false;
            }
        }
        return;
    }
    private static void printList(List<Integer> list){
        for(Integer e: list)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};
        List<List<Integer>> res = (new solu()).permute(nums);
        for(List<Integer> list: res)
            printList(list);
    }
}
